// 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。
// 需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

const removeDuplicateLetters = function (s: string): string {
    const lastIndex: number[] = new Array(26).fill(-1); // 存储字符最后一次出现的下标
    const originCode: number = 'a'.charCodeAt(0);
    // 记录字符最后一次出现的下标
    for (let i = 0; i < s.length; i++) {
        const currCode: number = s[i].charCodeAt(0);
        lastIndex[currCode - originCode] = Math.max(i, lastIndex[currCode - originCode]);
    }
    const stack: string[] = []; // 辅助栈
    const stackSet = new Set<string>(); // 哈希集合记录栈中出现过的字符
    // 开始扫描原字符
    for (let i = 0; i < s.length; i++) {
        if (stackSet.has(s[i])) continue; // 如果单调栈中出现了当前字符，直接舍弃
        let peak: string = stack[stack.length - 1];
        // 重要判断条件：栈顶存在元素且大于当前扫描元素且栈顶元素在剩余字符子串中仍会出现时，应该丢弃栈顶元素
        while (stack.length > 0 &&
            peak > s[i] &&
            lastIndex[peak.charCodeAt(0) - originCode] > i) {
            stackSet.delete(stack.pop()!); // 出栈并维护哈希集合
            peak = stack[stack.length - 1]; // 更新栈顶元素
        }
        // 加入元素并更新哈希集合
        stack.push(s[i]);
        stackSet.add(s[i]);
    }
    return stack.join('');
};


removeDuplicateLetters(
    "ecbacba")